class Solution {
    /*
    1、如果投A（当前元素等于A），则A的票数++;
    2、如果投B（当前元素等于B），B的票数++；
    3、如果A,B都不投（即当前与A，B都不相等）,那么检查此时A或B的票数是否减为0，如果为0,则当前元素成为新的候选人；如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均减一。

      思维点1：由于两个候选人不能相同，所以resA==i，resB==i这两个判断应该放在前面
      思维点2：resA和resB依然有可能相等
    */
    public List<Integer> majorityElement(int[] nums) {
        int countA = 0, countB = 0;  
        int resA = nums[0], resB = nums[0]; // 选择两个候选人
        for(int i : nums){
            if( resA==i ){ // 又有人选了候选人A
                countA ++;
            }else if( resB==i){
                countB ++;
            }else if( countA==0 ){ // 候选人A票数为0，则选择新的候选人
                resA = i;
                countA ++;
            }else if( countB==0 ){// 候选人B票数为0，则选择新的候选人
                resB = i;
                countB ++;
            }else{
                countA--;
                countB--;
            }
        }
         // 本题未保证一定存在2个候选人,因此还需要遍历一次确认是否大于1/3
        countA = 0;
        countB = 0;
        for(int i : nums){
            if( resA==i ) countA ++;
            else if( resB==i ) countB ++;
        }
        List ans = new ArrayList<>();
        if( countA>nums.length/3 )
            ans.add(resA);
        if( countB>nums.length/3 )
            ans.add(resB);
        // System.out.println(resA+", "+resB);
        return ans;
    }
}